#include "leetcode/leetcode.h"

class LRUCache {
    
    struct ListNode{
        int key;
        int val;
        ListNode* pre;
        ListNode* next;
        ListNode(): key(0), val(0), pre(nullptr), next(nullptr){}
        ListNode(int key_, int val_, ListNode* pre_, ListNode* next_): key(key_), val(val_), pre(pre_), next(next_){}
    };

    unordered_map<int, ListNode*> keymap;
    ListNode* head, *tail;
    int capacity_;

    void update_node(ListNode* node){
        ListNode* pre = node->pre;
        ListNode* next = node->next;
        pre->next = next;
        next->pre = pre;
        
        node->next = head->next;
        node->pre = head;
        head->next->pre = node;

        head->next = node;
    }

    ListNode* find_node(int key){
        auto it = keymap.find(key);
        if(it != keymap.end()){
            return it->second;
        }
        return nullptr;
    }

public:

    LRUCache(int capacity) {
        capacity_ = capacity;
        head = new ListNode();
        tail = new ListNode();
        head->next = tail;
        tail->pre = head;
    }

    ~LRUCache(){
        delete head;
        delete tail;
    }
    
    int get(int key) {
        
        ListNode* node = find_node(key);
        if(node != nullptr){
            update_node(node);
            return node->val;
        }
        else{
            return -1;
        }
    }
    
    void put(int key, int value) {
        
        ListNode* node = find_node(key);
        if(node != nullptr) {
            node->val = value;
            update_node(node);
        }
        else{
            ListNode* insert_node;
            if(keymap.size()>=capacity_){
                insert_node = tail->pre;
                keymap.erase(insert_node->key);
                insert_node->key = key;
                insert_node->val = value;
            }
            else{
                insert_node = new ListNode(key, value, head, head->next);
            }
            update_node(insert_node);
            keymap[key] = insert_node;
        }
    }
};
